
//1642.可以到达的最远建筑
class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        int n=heights.size();
        //先将每个房子之间的高度差进行统计
        vector<int> heidiff(n-1);
        for(int i=1;i<n;i++) 
        if(heights[i]>heights[i-1]) heidiff[i-1]=heights[i]-heights[i-1];

        //进行判断
        auto check=[&](int level){
            //模拟看能否到达level地方 level-1个间隔
            long long all=accumulate(heidiff.begin(),heidiff.begin()+level,0L);

            priority_queue<int,vector<int>,greater<int>> pq;  //找出ladders个最大的数
            for(int i=0;i<level&&ladders>0;i++) 
            {
                if(pq.size()<ladders)
                pq.push(heidiff[i]);
                else if(pq.top()<heidiff[i])
                {
                    pq.pop();
                    pq.push(heidiff[i]);
                
                }
            }
            //进行求和
            long long more=0;
            while(!pq.empty())
            {
                more+=pq.top();
                pq.pop();
            }
            return all-more<=bricks;
        };

        int left=0,right=n;
        while(left+1<right)
        {
            int mid=left+(right-left)/2;
            if(check(mid)) left=mid;
            else right=mid;
        }
        return left;
    }
};